//https://leetcode.cn/problems/find-original-array-from-doubled-array/description/?envType=daily-question&envId=2024-04-18


class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        unordered_map<int, int> ma;
        int n = changed.size();
        sort(changed.begin(), changed.end());
        for(int i = 0; i < n; i++)
        {
            ma[changed[i]]++;
        }
        vector<int> ans; 
        if(ma[0] % 2) return ans;
        for(int i = 0; i < n; i++)
        {
            if(ma[changed[i]])
            {
                if(!ma[changed[i] * 2]) return {};
                ans.push_back(changed[i]);
                ma[changed[i]]--;
                ma[changed[i] * 2]--;
            }
        }
        return ans;
    }
};